package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 删除有序链表重复元素
 * @date 24/5/4 20:26
 */
public class Leetcode083 {

	public static void main(String[] args) {
		ListNode head = ListNode.of(1, 1, 2, 3, 3);
		System.out.println(head);

		// ListNode newHead = deleteDuplicatesMyself(head);
		// ListNode newHead = deleteDuplicates(head);
		ListNode newHead = deleteDuplicatesRecursion(head);
		System.out.println(newHead);
	}

	/**
	 * 方法一：双指针比较【自己写的】
	 *
	 * @param head
	 * @return
	 */
	private static ListNode deleteDuplicatesMyself(ListNode head) {
		// 节点数<2时，直接返回
		if (head == null || head.next == null) {
			return head;
		}
		ListNode p1 = head;
		ListNode p2 = head.next;
		while (p2 != null) {
			// 相等情况下
			if (p1.val == p2.val) {
				p1.next = p2.next;
				p2 = p2.next;
			}
			else {
				p1 = p1.next;
				p2 = p2.next;
			}
		}
		return head;
	}

	/**
	 * 方法一：双指针比较【改进版】
	 *
	 * @param head
	 * @return
	 */
	private static ListNode deleteDuplicates(ListNode head) {
		// 节点数<2时，直接返回
		if (head == null || head.next == null) {
			return head;
		}
		ListNode p1 = head;
		// p2一开始不需要赋值，在循环时赋值
		ListNode p2;
		// 一开始就是给 p2 = p1.next
		while ((p2 = p1.next) != null) {
			// 相等情况下
			if (p1.val == p2.val) {
				p1.next = p2.next;
			}
			else {
				// p1向后平移【循环时，p2就会放到p1的next】
				p1 = p1.next;
			}
		}
		return head;
	}

	/**
	 * 方法二：递归实现
	 * 1 1 2 3 3
	 *
	 * @param p
	 * @return
	 */
	public static ListNode deleteDuplicatesRecursion(ListNode p) {
		// 节点<2
		if (p == null || p.next == null) {
			return p;
		}

		// 当前节点和下一个节点值相等
		if(p.val == p.next.val){
			// 直接进入递归，将下一个节点传进去
			return deleteDuplicatesRecursion(p.next);
		}
		else {
			p.next = deleteDuplicatesRecursion(p.next);
			return p;
		}

	}

}
